package com.hdu.other.dp.groupPakege;

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @link <a href="https://www.luogu.com.cn/problem/P1757">...</a>
 */
public class Template {
    private static final int MAX_N = 1001;
    private static final int[][] ARR = new int[MAX_N][3];
    private static int m, n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        StreamTokenizer st = new StreamTokenizer(br);

        while (st.nextToken() != StreamTokenizer.TT_EOF) {
            m = (int) st.nval;
            st.nextToken();
            n = (int) st.nval;
            for (int i = 1; i <= n; i++) {
                st.nextToken();
                ARR[i][0] = (int) st.nval;
                st.nextToken();
                ARR[i][1] = (int) st.nval;
                st.nextToken();
                ARR[i][2] = (int) st.nval;
            }

            Arrays.sort(ARR, 1, n + 1, Comparator.comparingInt(a -> a[2]));
            pw.println(compute());
        }

        pw.flush();
        pw.close();
        br.close();
    }

    public static int compute() {
        int groupSize = 1;
        for (int i = 2; i <= n; i++) {
            if (ARR[i][2] != ARR[i - 1][2]) {
                groupSize++;
            }
        }
        int[][] dp = new int[groupSize + 1][m + 1];

        for (int start = 1, end = 2, i = 1; start <= n; i++) {
            while (end <= n && ARR[end][2] == ARR[start][2]) {
                end++;
            }
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = start; k < end; k++) {
                    if (j >= ARR[k][0]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - ARR[k][0]] + ARR[k][1]);
                    }
                }
            }
            start = end++;
        }
        return dp[groupSize][m];
    }
}
